
local unpack
    = unpack
local floor
    = math.floor
local tremove
    = table.remove


module(...)


local function default_greater(a, b)
  return a > b
end

local function merge(left, right, greater)
  local result = {}
  while left[1] or right[1] do
    if left[1] and right[1] then
      if not greater(left[1], right[1]) then
        result[#result+1] = tremove(left, 1)
      else
        result[#result+1] = tremove(right, 1)
      end
    elseif left[1] then
      result[#result+1] = tremove(left, 1)
    elseif right[1] then
      result[#result+1] = tremove(right, 1)
    end
  end
  return result
end

function mergesort(t, greater)
  if not t[2] then
    return t
  end
  greater = greater or default_greater
  local middle = floor(#t / 2)
  local left = {unpack(t,1,middle)}
  local right = {unpack(t,middle+1)}
  left = mergesort(left, greater)
  right = mergesort(right, greater)
  return merge(left, right, greater)
end
